home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / BYACC__ / OUTPUT.C < prev    next >
C/C++ Source or Header  |  1989-11-19  |  11KB  |  708 lines
  1. #include <stdio.h>
  2. #include "action.h"
  3. #include "defs.h"
  4. #include "dep.h"
  5. #include "new.h"
  6. #include "files.h"
  7. #include "gram.h"
  8. #include "state.h"
  9.  
  10. extern action **parser;
  11. extern int final_state;
  12. extern core **state_table;
  13. extern shifts **shift_table;
  14. extern reductions **reduction_table;
  15. extern short *accessing_symbol;
  16. extern unsigned *LA;
  17. extern short *LAruleno;
  18. extern short *lookaheads;
  19. extern short *goto_map;
  20. extern short *from_state;
  21. extern short *to_state;
  22.  
  23. static int nvectors;
  24. static int nentries;
  25. static short **froms;
  26. static short **tos;
  27. static short *tally;
  28. static short *width;
  29. static short *state_count;
  30. static short *order;
  31. static short *base;
  32. static short *pos;
  33. static short *table;
  34. static short *check;
  35. static int lowzero;
  36. static int high;
  37.  
  38. output()
  39. {
  40.   free_itemsets();
  41.   free_shifts();
  42.   free_reductions();
  43.   fprintf(output_file, "\n#define YYQFINAL\t%d\n", final_state);
  44.   output_rule_data();
  45.   output_defred();
  46.   rm_defreds();
  47.   output_actions();
  48. }
  49.  
  50. output_rule_data()
  51. {
  52.   register int i;
  53.   register int j;
  54.  
  55.   fprintf(output_file, "\nshort yylhs[] = {%6d",
  56.        symbol_value[start_symbol]);
  57.  
  58.   j = 10;
  59.   for (i = 1; i < nrules; i++)
  60.     {
  61.       putc(',', output_file);
  62.  
  63.       if (j >= 10)
  64.     {
  65.       putc('\n', output_file);
  66.       j = 1;
  67.     }
  68.       else
  69.     {
  70.       j++;
  71.     }
  72.  
  73.       fprintf(output_file, "%6d", symbol_value[rlhs[i]]);
  74.     }
  75.  
  76.   FREE(rlhs);
  77.  
  78.   fprintf(output_file, "\n};\n\nshort yyrhslm1[] = {     0");
  79.  
  80.   j = 10;
  81.   for (i = 1; i < nrules; i++)
  82.     {
  83.       putc(',', output_file);
  84.  
  85.       if (j >= 10)
  86.     {
  87.       putc('\n', output_file);
  88.       j = 1;
  89.     }
  90.       else
  91.     {
  92.       j++;
  93.     }
  94.  
  95.       fprintf(output_file, "%6d", rrhs[i + 1] - rrhs[i] - 2);
  96.     }
  97.  
  98.   fprintf(output_file, "\n};\n");
  99.   FREE(rrhs);
  100. }
  101.  
  102. output_defred()
  103. {
  104.   register int i, j;
  105.  
  106.   fprintf(output_file, "\nshort yydefred[] = {%6d", defred[0]);
  107.  
  108.   j = 10;
  109.   for (i = 1; i < nstates; i++)
  110.     {
  111.       putc(',', output_file);
  112.       if (j < 10)
  113.     j++;
  114.       else
  115.     {
  116.       putc(NEWLINE, output_file);
  117.       j = 1;
  118.     }
  119.  
  120.       fprintf(output_file, "%6d", defred[i]);
  121.     }
  122.  
  123.   fprintf(output_file, "\n};\n");
  124. }
  125.  
  126. rm_defreds()
  127. {
  128.   register int i, found, ruleno;
  129.   register action *p;
  130.  
  131.   for (i = 0; i < nstates; i++)
  132.     {
  133.       ruleno = defred[i];
  134.       if (ruleno < 0)
  135.     continue;
  136.       for (p = parser[i]; p; p = p->next)
  137.     {
  138.       if (p->action_code == REDUCE && p->number == ruleno)
  139.         p->suppressed = 2;
  140.     }
  141.       found = 0;
  142.       for (p = parser[i]; p && ! found; p = p->next)
  143.     {
  144.       if (p->action_code != 0)
  145.         found = 1;
  146.     }
  147.       if (!found)
  148.     {
  149.       free_action_row(parser[i]);
  150.       parser[i] = 0;
  151.     }
  152.     }
  153. }
  154.  
  155. output_actions()
  156. {
  157.   nvectors = nstates + nvars;
  158.  
  159.   froms = NEW2(nvectors, short *);
  160.   tos = NEW2(nvectors, short *);
  161.   tally = NEW2(nvectors, short);
  162.   width = NEW2(nvectors, short);
  163.  
  164.   token_actions();
  165.   FREE(lookaheads);
  166.   FREE(LA);
  167.   FREE(LAruleno);
  168.   FREE(accessing_symbol);
  169.  
  170.   goto_actions();
  171.   FREE2(goto_map,ntokens);
  172.   FREE(from_state);
  173.   FREE(to_state);
  174.  
  175.   sort_actions();
  176.   pack_table();
  177.   output_base();
  178.   output_table();
  179.   output_check();
  180. }
  181.  
  182. token_actions()
  183. {
  184.   register int i, j, k;
  185.   register int max, min;
  186.   register short *actrow, *r, *s;
  187.   register action *p;
  188.  
  189.   actrow = NEW2(ntokens, short);
  190.   for (i = 0; i < final_state; i++)
  191.     {
  192.       if (parser[i])
  193.     {
  194.       for (j = 0; j < ntokens; j++)
  195.         actrow[j] = MINSHORT;
  196.  
  197.       for (p = parser[i]; p; p = p->next)
  198.         {
  199.           if (p->suppressed == 0)
  200.         {
  201.           if (p->action_code == SHIFT)
  202.             actrow[p->symbol] = p->number;
  203.           else if (p->action_code == REDUCE)
  204.             actrow[p->symbol] = - p->number;
  205.         }
  206.         }
  207.  
  208.       k = 0;
  209.       min = MAXSHORT;
  210.       max = 0;
  211.       for (j = 0; j < ntokens; j++)
  212.         {
  213.           if (actrow[j] != MINSHORT)
  214.         {
  215.           k++;
  216.           if (min > symbol_value[j])
  217.             min = symbol_value[j];
  218.           if (max < symbol_value[j])
  219.             max = symbol_value[j];
  220.         }
  221.         }
  222.  
  223.       if (k > 0)
  224.         {
  225.           froms[i] = r = NEW2(k, short);
  226.           tos[i] = s = NEW2(k, short);
  227.           for (j = 0; j < ntokens; j++)
  228.         {
  229.           if (actrow[j] != MINSHORT)
  230.             {
  231.               *r++ = symbol_value[j];
  232.               *s++ = actrow[j];
  233.             }
  234.         }
  235.           tally[i] = k;
  236.           width[i] = max - min + 1;
  237.         }
  238.     }
  239.     }
  240.   FREE(actrow);
  241. }
  242.  
  243. goto_actions()
  244. {
  245.   register int i, j, k;
  246.  
  247.   state_count = NEW2(nstates, short);
  248.  
  249.   k = default_goto(start_symbol);
  250.   fprintf(output_file, "\nshort yydefgoto[] = {%6d", k);
  251.   save_column(ntokens, k);
  252.  
  253.   j = 10;
  254.   for (i = ntokens + 1; i < nsyms; i++)
  255.     {
  256.       putc(',', output_file);
  257.  
  258.       if (j >= 10)
  259.     {
  260.       putc('\n', output_file);
  261.       j = 1;
  262.     }
  263.       else
  264.     {
  265.       j++;
  266.     }
  267.  
  268.       k = default_goto(i);
  269.       fprintf(output_file, "%6d", k);
  270.       save_column(i, k);
  271.     }
  272.  
  273.   fprintf(output_file, "\n};\n");
  274.   FREE(state_count);
  275. }
  276.  
  277. int
  278. default_goto(symbol)
  279. int symbol;
  280. {
  281.   register int i;
  282.   register int m;
  283.   register int n;
  284.   register int default_state;
  285.   register int max;
  286.  
  287.   m = goto_map[symbol];
  288.   n = goto_map[symbol + 1];
  289.  
  290.   if (m == n)
  291.     return (-1);
  292.  
  293.   for (i = 0; i < nstates; i++)
  294.     state_count[i] = 0;
  295.  
  296.   for (i = m; i < n; i++)
  297.     state_count[to_state[i]]++;
  298.  
  299.   max = 0;
  300.   default_state = -1;
  301.  
  302.   for (i = 0; i < nstates; i++)
  303.     {
  304.       if (state_count[i] > max)
  305.     {
  306.       max = state_count[i];
  307.       default_state = i;
  308.     }
  309.     }
  310.  
  311.   return (default_state);
  312. }
  313.  
  314.  
  315.  
  316. save_column(symbol, default_state)
  317. int symbol;
  318. int default_state;
  319. {
  320.   register int i;
  321.   register int m;
  322.   register int n;
  323.   register short *sp;
  324.   register short *sp1;
  325.   register short *sp2;
  326.   register int count;
  327.   register int symno;
  328.  
  329.   m = goto_map[symbol];
  330.   n = goto_map[symbol + 1];
  331.  
  332.   count = 0;
  333.   for (i = m; i < n; i++)
  334.     {
  335.       if (to_state[i] != default_state)
  336.     count++;
  337.     }
  338.  
  339.   if (count == 0)
  340.     return;
  341.  
  342.   symno = symbol - ntokens + nstates;
  343.  
  344.   froms[symno] = sp1 = sp = NEW2(count, short);
  345.   tos[symno] = sp2 = NEW2(count, short);
  346.  
  347.   for (i = m; i < n; i++)
  348.     {
  349.       if (to_state[i] != default_state)
  350.     {
  351.       *sp1++ = from_state[i];
  352.       *sp2++ = to_state[i];
  353.     }
  354.     }
  355.  
  356.   tally[symno] = count;
  357.   width[symno] = sp1[-1] - sp[0] + 1;
  358. }
  359.  
  360. sort_actions()
  361. {
  362.   register int i;
  363.   register int j;
  364.   register int k;
  365.   register int t;
  366.   register int w;
  367.  
  368.   order = NEW2(nvectors, short);
  369.   nentries = 0;
  370.  
  371.   for (i = 0; i < nvectors; i++)
  372.     {
  373.       if (tally[i] > 0)
  374.     {
  375.       t = tally[i];
  376.       w = width[i];
  377.       j = nentries - 1;
  378.  
  379.       while (j >= 0 && (width[order[j]] < w))
  380.         j--;
  381.  
  382.       while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
  383.         j--;
  384.  
  385.       for (k = nentries - 1; k > j; k--)
  386.         order[k + 1] = order[k];
  387.  
  388.       order[j + 1] = i;
  389.       nentries++;
  390.     }
  391.     }
  392. }
  393.  
  394. pack_table()
  395. {
  396.   register int i;
  397.   register int place;
  398.   register int state;
  399.  
  400.   base = NEW2(nvectors, short);
  401.   pos = NEW2(nentries, short);
  402.   table = NEW2(MAXSHORT, short);
  403.   check = NEW2(MAXSHORT, short);
  404.  
  405.   lowzero = 0;
  406.   high = 0;
  407.  
  408.   for (i = 0; i < nvectors; i++)
  409.     base[i] = MINSHORT;
  410.  
  411.   for (i = 0; i < MAXSHORT; i++)
  412.     check[i] = -1;
  413.  
  414.   for (i = 0; i < nentries; i++)
  415.     {
  416.       state = matching_state(i);
  417.  
  418.       if (state < 0)
  419.     place = pack_vector(i);
  420.       else
  421.     place = base[state];
  422.  
  423.       pos[i] = place;
  424.       base[order[i]] = place;
  425.     }
  426.  
  427.   for (i = 0; i < nvectors; i++)
  428.     {
  429.       FREE(froms[i]);
  430.       FREE(tos[i]);
  431.     }
  432.  
  433.   FREE(froms);
  434.   FREE(tos);
  435.   FREE(pos);
  436. }
  437.  
  438. int
  439. matching_state(vector)
  440. int vector;
  441. {
  442.   register int i;
  443.   register int j;
  444.   register int k;
  445.   register int t;
  446.   register int w;
  447.   register int match;
  448.   register int prev;
  449.  
  450.   i = order[vector];
  451.   if (i >= nstates)
  452.     return (-1);
  453.  
  454.   t = tally[i];
  455.   w = width[i];
  456.  
  457.   for (prev = vector - 1; prev >= 0; prev--)
  458.     {
  459.       j = order[prev];
  460.       if (width[j] != w || tally[j] != t)
  461.     return (-1);
  462.  
  463.       match = 1;
  464.       for (k = 0; match && k < t; k++)
  465.     {
  466.       if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
  467.         match = 0;
  468.     }
  469.  
  470.       if (match)
  471.     return (j);
  472.     }
  473.  
  474.   return (-1);
  475. }
  476.  
  477.  
  478.  
  479. int
  480. pack_vector(vector)
  481. int vector;
  482. {
  483.   register int i, j, k;
  484.   register int t;
  485.   register int loc;
  486.   register int ok;
  487.   register short *from;
  488.   register short *to;
  489.  
  490.   i = order[vector];
  491.   t = tally[i];
  492.   if (t == 0)
  493.     panic("pack_vector");
  494.  
  495.   from = froms[i];
  496.   to = tos[i];
  497.  
  498.   for (j = lowzero - from[0]; j < MAXSHORT; j++)
  499.     {
  500.       ok = 1;
  501.       for (k = 0; ok && k < t; k++)
  502.     {
  503.       loc = j + from[k];
  504.       if (loc > MAXSHORT)
  505.         fatal("maximum table size exceeded");
  506.  
  507.       if (check[loc] != -1)
  508.         ok = 0;
  509.     }
  510.       for (k = 0; ok && k < vector; k++)
  511.     {
  512.       if (pos[k] == j)
  513.         ok = 0;
  514.     }
  515.       if (ok)
  516.     {
  517.       for (k = 0; k < t; k++)
  518.         {
  519.           loc = j + from[k];
  520.           table[loc] = to[k];
  521.           check[loc] = from[k];
  522.           if (loc > high)
  523.         high = loc;
  524.         }
  525.  
  526.       while (check[lowzero] != -1)
  527.         lowzero++;
  528.  
  529.       return (j);
  530.     }
  531.     }
  532.  
  533.   panic("pack_vector");
  534. }
  535.  
  536.  
  537.  
  538. output_base()
  539. {
  540.   register int i;
  541.   register int j;
  542.  
  543.   for (i = 0; i < nstates; i++)
  544.     {
  545.       j = base[i];
  546.       if (j == MINSHORT)
  547.     {
  548.       j = defred[i];
  549.       if (j >= 0)
  550.         base[i] = j;
  551.     }
  552.       else
  553.     base[i] = j - high;
  554.     }
  555.       
  556.  
  557.   fprintf(output_file, "\nshort yyrowbase[] = {%6d", base[0]);
  558.  
  559.   j = 10;
  560.   for (i = 1; i < nstates; i++)
  561.     {
  562.       putc(',', output_file);
  563.  
  564.       if (j >= 10)
  565.     {
  566.       putc('\n', output_file);
  567.       j = 1;
  568.     }
  569.       else
  570.     {
  571.       j++;
  572.     }
  573.  
  574.       fprintf(output_file, "%6d", base[i]);
  575.     }
  576.  
  577.   fprintf(output_file, "\n};\n\nshort yycolumnbase[] = {%6d", base[nstates]);
  578.  
  579.   j = 10;
  580.   for (i = nstates + 1; i < nvectors; i++)
  581.     {
  582.       putc(',', output_file);
  583.  
  584.       if (j >= 10)
  585.     {
  586.       putc('\n', output_file);
  587.       j = 1;
  588.     }
  589.       else
  590.     {
  591.       j++;
  592.     }
  593.  
  594.       fprintf(output_file, "%6d", base[i]);
  595.     }
  596.  
  597.   fprintf(output_file, "\n};\n");
  598.   FREE(base);
  599. }
  600.  
  601.  
  602.  
  603. output_table()
  604. {
  605.   register int i;
  606.   register int j;
  607.  
  608.   fprintf(output_file, "\n\n#define\tYYTABLESIZE\t\t%d\n\n", high);
  609.   fprintf(output_file, "\nshort yytable[] = {%6d", table[0]);
  610.  
  611.   j = 10;
  612.   for (i = 1; i <= high; i++)
  613.     {
  614.       putc(',', output_file);
  615.  
  616.       if (j >= 10)
  617.     {
  618.       putc('\n', output_file);
  619.       j = 1;
  620.     }
  621.       else
  622.     {
  623.       j++;
  624.     }
  625.  
  626.       fprintf(output_file, "%6d", table[i]);
  627.     }
  628.  
  629.   fprintf(output_file, "\n};\n");
  630.   FREE(table);
  631. }
  632.  
  633.  
  634.  
  635. output_check()
  636. {
  637.   register int i;
  638.   register int j;
  639.  
  640.   fprintf(output_file, "\nshort yycheck[] = {%6d", check[0]);
  641.  
  642.   j = 10;
  643.   for (i = 1; i <= high; i++)
  644.     {
  645.       putc(',', output_file);
  646.  
  647.       if (j >= 10)
  648.     {
  649.       putc('\n', output_file);
  650.       j = 1;
  651.     }
  652.       else
  653.     {
  654.       j++;
  655.     }
  656.  
  657.       fprintf(output_file, "%6d", check[i]);
  658.     }
  659.  
  660.   fprintf(output_file, "\n};\n");
  661.   FREE(check);
  662. }
  663.  
  664.  
  665. free_itemsets()
  666. {
  667.   register core *cp;
  668.   register core *cp2;
  669.  
  670.   FREE(state_table);
  671.  
  672.   for (cp = first_state; cp;){
  673.       cp2 = cp;
  674.       cp = cp->next;
  675.     FREE(cp2);
  676.   }
  677. }
  678.  
  679.  
  680.  
  681. free_shifts()
  682. {
  683.   register shifts *sp,*sp2;
  684.  
  685.   FREE(shift_table);
  686.  
  687.   for (sp = first_shift; sp; ){
  688.       sp2 = sp;
  689.       sp = sp->next;
  690.     FREE(sp2);
  691.   }
  692. }
  693.  
  694.  
  695.  
  696. free_reductions()
  697. {
  698.   register reductions *rp,*rp2;
  699.  
  700.   FREE(reduction_table);
  701.  
  702.   for (rp = first_reduction; rp;){
  703.       rp2 = rp;
  704.       rp = rp->next;
  705.     FREE(rp2);
  706.   }
  707. }
  708.